

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int findMaxLength(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 2)
            return 0;

        int res = 0;
        unordered_map<int, int> prefixsum{ {0, -1} };

        for (int end = 0, sum = 0; end < n; ++end)
        {
            sum += nums[end] ? 1 : -1;

            if (prefixsum.count(sum))
                res = max(res, end - prefixsum[sum]);
            else
                prefixsum[sum] = end;
        }

        return res;
    }

    vector<vector<int>> merge1(vector<vector<int>>& intervals)
    {
        int n = intervals.size();
        vector<vector<int>> res;

        for (int i = 0; i < n;)
        {
            int flag = 1;

            for (int j = 0; j < n; ++j)
            {
                if (j != i)
                {
                    int beg1 = intervals[i][0], end1 = intervals[i][1];
                    int beg2 = intervals[j][0], end2 = intervals[j][1];

                    if (!(end1 < beg2 || beg1 > end2))
                    {
                        intervals[i] = { min(beg1, beg2), max(end1, end2) };
                        swap(intervals[j], intervals[n - 1]);
                        --n;
                        flag = 0;
                    }
                }
            }
            if (flag)
                ++i;
        }

        for (int i = 0; i < n; ++i)
        {
            res.push_back(intervals[i]);
        }

        return res;
    }

    vector<vector<int>> merge2(vector<vector<int>>& intervals)
    {
        int n = intervals.size();
        if (n < 2)
            return intervals;

        vector<vector<int>> res;

        sort(intervals.begin(), intervals.end());
        for (int i = 0; i < n; ++i)
        {
            int beg = intervals[i][0], end = intervals[i][1];

            if (res.empty() || res.back()[1] < beg)
            {
                res.push_back(intervals[i]);
            }
            else
            {
                res.back() = { min(res.back()[0], beg), max(res.back()[1], end) };
            }
        }

        return res;
    }
};

void Test1()
{
    vector<vector<int>> vv1{ {1,3},{2,6},{8,10},{15,18 } };
    vector<vector<int>> vv2{ {2, 3}, { 4, 5 }, { 6, 7 }, {8, 9}, { 1, 10 }};

    Solution().merge2(vv2);
}

int main()
{
    Test1();

	return 0;
}